package algo.graph;

import ds.adt.Digraph;

public class DirectedDFS {

	private boolean[] marked;
	private int count;

	public DirectedDFS(Digraph g, int s) {
		this.marked = new boolean[g.V()];
		this.count = 0;

		dfs(g, s);
	}

	public DirectedDFS(Digraph g, Iterable<Integer> sources) {
		this.marked = new boolean[g.V()];
		this.count = 0;

		for (int i : sources) {
			if (!marked[i]) {
				dfs(g, i);
			}
		}
	}

	private void dfs(Digraph g, int v) {
		marked[v] = true;
		count++;

		for (int w : g.adj(v)) {
			if (!marked[w]) {
				dfs(g, w);
			}
		}
	}

	public boolean marked(int v) {
		return marked[v];
	}

	public int count() {
		return count;
	}

	public static void main(String[] args) {

		Digraph g = new Digraph(5);
		g.addEdge(0, 1);
		g.addEdge(1, 2);
		g.addEdge(0, 3);
		g.addEdge(0, 4);

		System.out.println("Graph Adjaceny List =" + g.toString());

		DirectedDFS dfs = new DirectedDFS(g, 0);
		System.out.print("DFS PATH : ");
		for (int i = 0; i < g.V(); i++) {
			if (dfs.marked(i)) {
				System.out.print(i);
			}
		}
	}
}
